

def parse1(s):
    acc = [[]]
    for ch in s:
        if ch == '(':
            acc.append([])
        elif ch == ')':
            if len(acc) == 1:
                raise Exception("more ')'")
            last = acc.pop()
            acc[-1].append(last)
        else:
            acc[-1].append(ch)
    if len(acc) != 1:
        raise Exception("less ')'")
    return acc.pop()

class LineMach:
    def __init__(self):    # 不用处理错误，直接中断+err置1
        self.rules = []

    def reg(self, state, a):
        def g(f):
            self.rules.append(((state, a), f))
        return g

    def run(self, data, debug=True):
        state = Ss()
        data += ["end"]
        for a in data:
            state = self.reduction(state, a, debug)
        assert isinstance(state, Xs)
        #print(repr3(state.x))
        return state.x

    def reduction(self, state, a, debug):
        for (t1, t2), f in self.rules:
            if match(state, t1) and match(a, t2):
                if debug:
                    print("match from", state, a)
                    print( "match", repr2(t1), repr2(t2))
                r = f(state, a)
                if debug:
                    print("to", r)
                return r
        else:
            print("err1", state, repr(a))
            raise Exception("无可匹配的规则")

lm = LineMach()

class State:
    def __repr__(self):
        return f"<{type(self).__name__}>"


class Ss(State):
    def __init__(self):
        pass


class Xs(State):
    def __init__(self, x):
        self.x = x


class Fs(State):
    def __init__(self, last, f, k):
        self.last = last
        self.f = f
        self.k = k      # 左右结合权重



class Fxs(State):
    def __init__(self, last, f, x, k):
        self.last = last
        self.f = f
        self.x = x
        self.k = k      # 左右结合权重


def repr2(pattern):
    if isinstance(pattern, type):
        return pattern.__name__
    elif isinstance(pattern, list):
        s = ', '.join(repr2(x) for x in pattern)
        return "[" + s + "]"
    elif callable(pattern):
        return pattern.__name__
    else:
        return pattern.__repr__()

def repr3(tree):
    if isinstance(tree, list):
        s = ', '.join(repr3(x) for x in tree)
        return "[" + s + "]"
    elif isinstance(tree, str):
        return tree
    else:
        #print(type(tree))
        return repr(tree)


def match(x, pattern):
    if isinstance(pattern, type):
        return isinstance(x, pattern)
    elif isinstance(pattern, list):
        flag = False
        for p2 in pattern:
            if match(x, p2):
                flag = True
                break
        return flag
    elif callable(pattern):
        return pattern(x)
    else:
        return x == pattern


table_op2 = {}
table_head = {}

table_head['x'] = 5
table_head['y'] = 5
table_head['z'] = 5
table_op2['+'] = 3
table_op2['-'] = 3

@lm.reg(Ss, list("xyz"))
def f(ss, a):
    return Fs(None, [a], table_head[a])

@lm.reg(Fs, list("123456789"))
def f(fs, a):
    # ~ print("start", fs.f)
    return Fxs(fs.last, fs.f, a, fs.k)

@lm.reg(Fxs, list("123456789"))
def f(fxs, a):
    if len(fxs.x) <= 2:
        return Fxs(fxs.last, fxs.f + [fxs.x], a, fxs.k)
    else:
        raise Exception("x1111")

@lm.reg(Fxs, list("+-"))
def f(fxs, a):
    opk = table_op2[a]
    if fxs.k >= opk:
        while fxs.last is not None and fxs.last.k >= opk:
            fs = fxs.last
            fxs = Fxs(fs.last, fs.f, fxs.f + [fxs.x], fs.k)
        return Fs(fxs.last, [a, fxs.f + [fxs.x]], opk)
    else:
        loser = Fs(fxs.last, fxs.f, fxs.k)
        return Fs(loser, [a, fxs.x], opk)


@lm.reg(Fs, list)
def f(fs, a):
    a = parse2(a)
    return Fxs(fs.last, fs.f, a, fs.k)

@lm.reg(Fs, list("xyz"))
def f(fs, a):
    return Fs(fs, [a], table_head[a])

@lm.reg(Fxs, "end")
def f(fxs, a):
    while fxs.last is not None:
        fs = fxs.last
        fxs = Fxs(fs.last, fs.f, fxs.f + [fxs.x], fs.k)
    return Xs(fxs.f + [fxs.x])


from itertools import product

def box_eval(tree):
    if tree[0] == 'x':
        body = [int(a) for a in tree[1:]]
        if len(body) == 1:
            x, = body
            hx = x // 2
            return list(product(range(-hx, x-hx), range(1), range(1)))
        elif len(body) == 2:
            y, z = body
            hy, hz = y // 2, z // 2
            return list(product(range(1), range(-hy, y-hy), range(-hz, z-hz)))
        elif len(body) == 3:
            x, y, z = body
            hx, hy, hz = x // 2, y // 2, z // 2
            return list(product(range(-hx, x-hx), range(-hy, y-hy), range(-hz, z-hz)))
    elif tree[0] == 'y':
        body = [int(a) for a in tree[1:]]
        if len(body) == 1:
            y, = body
            hy = y // 2
            return list(product(range(1), range(-hy, y-hy), range(1)))
        elif len(body) == 2:
            x, z = body
            hx, hz = x // 2, z // 2
            return list(product(range(-hx, x-hx), range(1), range(-hz, z-hz)))
        elif len(body) == 3:
            y, x, z = body
            hx, hy, hz = x // 2, y // 2, z // 2
            return list(product(range(-hx, x-hx), range(-hy, y-hy), range(-hz, z-hz)))
    elif tree[0] == 'z':
        body = [int(a) for a in tree[1:]]
        if len(body) == 1:
            z, = body
            hz = z // 2
            return list(product(range(1), range(1), range(-hz, z-hz)))
        elif len(body) == 2:
            x, y = body
            hx, hy = x // 2, y // 2
            return list(product(range(-hx, x-hx), range(-hy, y-hy), range(1)))
        elif len(body) == 3:
            z, x, y = body
            hx, hy, hz = x // 2, y // 2, z // 2
            return list(product(range(-hx, x-hx), range(-hy, y-hy), range(-hz, z-hz)))
    elif tree[0] == '+':
        a1, a2 = tree[1:]
        a1 = box_eval(a1)
        a2 = box_eval(a2)
        acc = a1.copy()
        for pos in a2:
            if pos not in a1:
                acc.append(pos)
        return acc
    elif tree[0]  == '-':
        a1, a2 = tree[1:]
        a1 = box_eval(a1)
        a2 = box_eval(a2)
        acc = []
        for pos in a1:
            if pos not in a2:
                acc.append(pos)
        acc.sort()
        return acc

def parse2(l):
    return lm.run(l, debug=False)
    # ~ return lm.run(l, debug=True)


def ana(code):
    r = parse1(code)
    r2 = parse2(r)
    r3 = box_eval(r2)
    return r3


if __name__ == "__main__":
    # ~ code = "x333-(y33-z3)"
    # ~ code = "x3+y3+z3"
    code = "x333-(x3+y3+z3)"
    # ~ code = "x1+x1+x1"
    # ~ code = "x333-(y33-z3)+x1"
    # ~ code = "x11+(x11-x11)"
    # ~ code = "x333-1"
    # ~ code = "y33"


    r = parse1(code)
    print(r)
    r = parse2(r)
    print(r)

    from tool_treeprint import tree

    def name(o):
        if isinstance(o, (tuple, list)):
            return o[0]
        else:
            return str(o)

    def member(o):
        if isinstance(o, (tuple, list)):
            return list(o[1:])
        else:
            return []

    tree(r, name, member)



    r = box_eval(r)
    print(len(r))
    print(r)
















